package leetcode.code0903;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	char[] di;
	int n;

	int mod = (int) 1e9 + 7;

	public int numPermsDISequence(String s) {
		di = s.toCharArray();
		n = s.length();// [0,n]
		long ans = 0;
		Integer[][] dp = new Integer[n][n + 1];
		for (int i = 0; i <= n; i++) {
			// 第0个位置拿i，有多少种拿法满足序列S的要求。此时剩余比i小的数有i个
			ans += f(0, i, dp);
			ans %= mod;
		}
		return (int) ans;
	}

	// 第index位置做了选择后，剩下smaller个数比当前选择的小
	private long f(int index, int smaller, Integer[][] dp) {
		if (index == n) {// 顺利选完，这是一种有效的选择方法
			return 1;
		}
		if (dp[index][smaller] != null) {
			return dp[index][smaller];
		}
		int rest = n + 1 - (index + 1);// 总共n + 1个数，用掉 index + 1 个剩下rest个
		int bigger = rest - smaller;// 比index小的数量是smaller个，比index大的数量是bigger个
		char curid = di[index];// 当前参照di值，由这个di值决定后续从大的中选还是从小的中选。
		long ans = 0;
		if (curid == 'D') {// 当前是D，要比前一个index位置小，从smaller里面挑一个，挑第i个
			for (int i = 0; i < smaller; i++) {
				ans += f(index + 1, i, dp);
				ans %= mod;
			}
		} else {// 当前是I 从bigger里面挑一个，挑第i个
			for (int i = 0; i < bigger; i++) {
				ans += f(index + 1, smaller + i, dp);// 剩下smaller + i个小于当前选择的数
				ans %= mod;
			}
		}
		dp[index][smaller] = (int) ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(2, this.numPermsDISequence("DI"));
		H.compare(5, this.numPermsDISequence("DID"));
		H.compare(1, this.numPermsDISequence("D"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int mod = (int) 1e9 + 7;
		System.out.println(11458373181l % mod);
	}

}
